\documentclass[12pt,a4paper,french]{book}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage{a4}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{framed}
\usepackage{dsfont}
\usepackage[amsmath,thmmarks,thref,framed]{ntheorem}
\usepackage[dvips]{graphics}
\usepackage{epsfig}
\usepackage{calc}
\usepackage{tabls}
\usepackage{slashbox}
\usepackage{times}
\usepackage{tabularx}
\usepackage{textcomp}

\usepackage{pst-all}

\begin{document}
\includegraphics{figures/LogoIUT.eps}
\begin{center}
\begin{Huge}
Partiel de : Théorie des graphes\\
Semestre 3 (23 mars 2009)\\
\end{Huge}
\end{center}

La calculatrice, ainsi qu'un quart de feuille A4, sont autorisés. Ce sujet contient 50 affirmations justes, et 50 fausses. Vous aurez +1 à chaque valeur de vérité trouvée, -1 à chaque erreur (et 0 en absence de réponse). Les notes seront ajustées à l'intervalle $[0;20]$ (les notes négatives auront 0).\\

Q. 1. Les graphes hamiltoniens ont été définis au dix-neuvième siècle.\\

Q. 2. Une chaîne dans lequel tous les sommets sont différents s’appelle une chaîne simple.\\

Q. 3. Un graphe hamiltonien peut posséder un sommet de degré 2.\\

Q. 4. Soit $J$ la matrice d'adjacence d'un graphe non orienté. $J_{s,\varepsilon}$ vaut :
\begin{itemize}
\item 1 quand $s$ est une extrémité de l'arête $\varepsilon$ si celle-ci n'est pas une boucle,
\item 2 quand $s$ est une extrémité de la boucle $\varepsilon$,
\item 0 si $s$ n'est pas une extrémité de $\varepsilon$.
\end{itemize}

Q. 5. Un graphe hamiltonien peut posséder un sommet de degré 3.L'assertion proposée est vraie ou fausse\\

Q. 6. La matrice d'adjacence d'un graphe non orienté est symétrique.\\

Q. 7. Un graphe est dit planaire si on arrive à le dessiner sans qu'aucune arête n'en coupe une autre.\\

Q. 8. L'inventeur des nombres complexes est aussi l'inventeur des graphes euleriens.\\

Q. 9. Un circuit eulérien est un circuit qui passe par tous les sommets du graphe.\\

Q. 10. Soit G un graphe connexe non eulérien. Il est toujours possible de rendre G eulérien en lui rajoutant un sommet et quelques arêtes.\\

Q. 11. S'il existe un sommet qui est connecté à tous les autres, alors le graphe considéré est connexe.\\

Q. 12. Le graphe suivant est biparti.

\begin{center}
\includegraphics[scale=0.7]{figures/completK5.eps}
\end{center}

Q. 13. Dans une matrice d'incidence, la somme des coefficients de la ligne $i$ est le degré du sommet $i$.\\

Q. 14.
Le graphe $G$ :

\begin{center}
\includegraphics[scale=0.75]{figures/graphe1bx.eps}
\end{center}

a pour matrice d'incidence :

$$M = \left(
\begin{array}{ccccc}
0 ~~ 0 ~~ 1 ~~ 1 ~~ 1\\
0 ~~ 0 ~~ 1 ~~ 0 ~~ 0\\
1 ~~ 1 ~~ 0 ~~ 1 ~~ 1\\
1 ~~ 0 ~~ 1 ~~ 0 ~~ 1\\
1 ~~ 0 ~~ 1 ~~ 1 ~~ 0\\
\end{array}
\right)
$$\\

Q. 15. Le graphe suivant est biparti.

\begin{center}
\includegraphics[scale=0.7]{figures/arbre1.eps}
\end{center}

Q. 16. $K_6$ est complet.\\

Q. 17. Le graphe suivant est complet

\begin{center}
\includegraphics[scale=0.7]{figures/biparti.eps}
\end{center}

Q. 18. Un graphe est dit planaire si toutes ses représentations sont telles qu'aucune arête n'en coupe une autre.\\

Q. 19. Une chaîne dont le départ et l'arrivée coïncident s'appelle un chemin.\\

Q. 20. Le graphe suivant est eulérien

\begin{center}
\includegraphics[scale=0.7]{figures/grapheNonConnexe.eps}
\end{center}

Q. 21. Le graphe ci-dessous est eulérien.

\begin{center}
\includegraphics[scale=0.7]{figures/arbre1.eps}
\end{center}

Q. 22. La question à l'origine du problème des graphes hamiltoniens est : comment passer une, et une seule fois, par chacun des sommets du dodécaèdre, de telle manière que le dernier sommet visité est aussi le premier.\\

Q. 23. Un arbre est un graphe non orienté.\\

Q. 24. Le graphe suivant est connexe.

\begin{center}
\includegraphics[scale=0.7]{figures/completK5.eps}
\end{center}

Q. 25. Un arbre est un graphe non orienté sans cycle.\\

Q. 26. Les expressions chaîne simple et chemin sont synonymes.\\

Q. 27. Le graphe suivant est eulerien.

\begin{center}
\includegraphics[scale=0.7]{figures/completK5.eps}
\end{center}

Q. 28. La matrice d'incidence est carrée.\\

Q. 29. $K_{m,n}$ possède $m+n$ arêtes.\\

Q. 30. Le degré du graphe suivant est 5.

\begin{center}
\includegraphics[scale=0.7]{figures/completK5.eps}
\end{center}

Q. 31. Le graphe suivant est planaire.

\begin{center}
\includegraphics[scale=0.7]{figures/completK5.eps}
\end{center}

Q. 32. Le degré du graphe suivant est 20.

\begin{center}
\includegraphics[scale=0.7]{figures/completK5.eps}
\end{center}

Q. 33. Un graphe est connexe s'il est possible, à partir de n'importe quel sommet, d'atteindre n'importe quel autre sommet du graphe.\\

Q. 34.
Soit G un graphe. Le graphe G' est un graphe partiel de G, si on obtient G' en enlevant un ou plusieurs sommets au graphe G (avec les arêtes associées).\\

Q. 35. $K_n$ possède $n^2$ arêtes.\\

Q. 36. Le graphe suivant est biparti

\begin{center}
\includegraphics[scale=0.7]{figures/grapheNonConnexe.eps}
\end{center}

Q. 37.
On considère des dominos dont les faces sont numérotées 1, 2, 3, 4 ou 5. Il est toujours possible d'arranger ces dominos de manière à former une boucle fermée.\\

Q. 38. Le nombre maximal d'arêtes dans un graphe non orienté d'ordre $n$ qui ne possède ni arêtes parallèles, ni boucles, est de $n^{2}$.\\

Q. 39. Tous les $K_n$ sont hamiltoniens.\\

Q. 40. Il existe des graphes 3-réguliers simples à 6 sommets.\\

Q. 41.
Représenter un graphe sous la forme d'une liste d'adjacence consiste à donner, pour chacun de ses sommets, la liste des sommets auxquels il est adjacent.\\

Q. 42.
On appelle chaîne eulérienne une chaîne contenant une et une seule fois toutes les arêtes du graphe.\\

Q. 43.
La question à l'origine du problème des graphes hamiltoniens est : comment passer une, et une seule fois, par chacun des sommets du dodécaèdre.\\

Q. 44. Si le graphe considéré n'a pas de boucle, alors la matrice d'adjacence associée a une diagonale nulle.\\

Q. 45. Il peut y avoir plusieurs circuits hamiltoniens dans un graphe hamiltonien.\\

Q. 46. Le graphe suivant est simple

\begin{center}
\includegraphics[scale=0.7]{figures/grapheNonSimple.eps}
\end{center}

Q. 47. Pour tout $n$, $K_n$ est complet.\\

Q. 48. Un graphe hamiltonien peut posséder un sommet de degré 3.\\

Q. 49. Un circuit eulérien est un circuit qui passe par toutes les arêtes du graphe.L'assertion proposée est vraie ou fausse\\

Q. 50. $K_n$ possède $\dfrac{n(n-1)}{2}$ sommets.\\

Q. 51. Le graphe suivant est hamiltonien.

\begin{center}
\includegraphics[scale=0.7]{figures/completK5.eps}
\end{center}

Q. 52.
\begin{center}
\includegraphics[scale=0.7]{figures/graphe9.eps}
\end{center}

est un sous-graphe de

\begin{center}
\includegraphics[scale=0.7]{figures/graphe7.eps}
\end{center}

Q. 53. Hamilton est à l'origine du problème des graphes eulériens.\\

Q. 54. Un graphe hamiltonien ne possède pas de sommets de degré 1.L'assertion proposée est vraie ou fausse\\

Q. 55. Le corollaire de Dirac se déduit du théorème de Ore.L'assertion proposée est vraie ou fausse\\

Q. 56.
Posséder un circuit eulérien est équivalent à n'avoir aucun sommet de degré impair.\\

Q. 57. Un circuit hamiltonien est un circuit qui passe par toutes les arêtes du graphe.\\

Q. 58. Il existe des graphes qui peuvent être hamiltoniens sans être eulériens.\\

Q. 59. $K_5$ est hamiltonien.\\

Q. 60.
\begin{center}
\includegraphics[scale=0.7]{figures/graphe9.eps}
\end{center}

est un stable de

\begin{center}
\includegraphics[scale=0.7]{figures/graphe7.eps}
\end{center}

Q. 61. Dans le cas des graphes orientés, on parle de chemins, et dans le cas non orienté, de chaînes.\\

Q. 62. Dans le graphe suivant, le sommet 1 a pour degré 4.

\begin{center}
\includegraphics[scale=0.7]{figures/completK5.eps}
\end{center}

Q. 63. Le graphe suivant est connexe.

\begin{center}
\includegraphics[scale=0.7]{figures/biparti.eps}
\end{center}

Q. 64.
Dans un circuit eulérien, le point de départ et d'arrivée coïncident.\\

Q. 65. Le théorème de Ore s'énonce ainsi : Soit G = (V, E) un graphe simple d'ordre $n\geqslant 3$. Si pour toute paire \{x,y\} de sommets non adjacents, on a $d(x) + d(y) \geqslant n$, alors G est hamiltonien.\\

Q. 66.
Etre un graphe eulérien est équivalent à être connexe, sans sommet de degré impair.\\

Q. 67. Un circuit hamiltonien est un circuit qui passe par tous les sommets du graphe.L'assertion proposée est vraie ou fausse\\

Q. 68.
\begin{center}
\includegraphics[scale=0.7]{figures/graphe8.eps}
\end{center}

est un sous-graphe partiel de

\begin{center}
\includegraphics[scale=0.7]{figures/graphe7.eps}
\end{center}

Q. 69.
Posséder un circuit eulérien est équivalent à avoir 0 ou 2 sommets de degré impair.\\

Q. 70. Un graphe est dit complet s'il est en un seul tenant.\\

Q. 71.
Etre un graphe eulérien est équivalent à n'avoir aucun sommet de degré impair.\\

Q. 72.
Le graphe suivant est-il eulérien ?

\begin{center}
\includegraphics[scale=0.7]{figures/eulerKonig}
\end{center}

Q. 73. Il existe des graphes 3-réguliers simples à 8 sommets.\\

Q. 74. Le graphe suivant s'appelle $K_5$.

\begin{center}
\includegraphics[scale=0.7]{figures/completK5.eps}
\end{center}

Q. 75. Un graphe hamiltonien ne possède pas de sommets de degré 1.\\

Q. 76. $K_{m,n}$ désigne tout graphe ayant deux composantes connexes, la première avec $m$ sommets, et la seconde avec $n$ sommets.\\

Q. 77. Un graphe connexe est complet.\\

Q. 78. Le corollaire de Dirac sert à déterminer si un graphe est eulérien.L'assertion proposée est vraie ou fausse\\

Q. 79. Le degré d'un graphe est son nombre d'arêtes.\\

Q. 80. Un graphe dont tous les sommets ont le même degré est dit régulier.\\

Q. 81.
Etre un graphe eulérien est équivalent à être connexe, avec 0 ou 2 sommets de degré impair.\\

Q. 82. Le nombre maximal d'arêtes dans un graphe non orienté d'ordre $n$ qui ne possède pas d'arêtes parallèles, est de $n^{2}$.\\

Q. 83.
Posséder une chaîne eulérienne est équivalent à être connexe, sans sommet de degré impair.\\

Q. 84.
Le graphe $(S',A')$ est un sous-graphe du graphe $(S,A)$ si
\begin{enumerate}
\item $S' \subset S$,
\item $A' \subset A$,
\item $A'=\{(x,y)\mid (x,y) \in A \land x \in S' \land y \in S'\}$
\end{enumerate}

Q. 85.
On considère des dominos dont les faces sont numérotées de 1 à 7. Il est toujours possible d'arranger ces dominos de manière à former une boucle fermée.\\

Q. 86.
Un graphe eulérien est un graphe possédant un circuit eulérien.\\

Q. 87. Le corollaire de Dirac s'énonce ainsi : Soit G = (V, E) un graphe simple d'ordre $n\geqslant 3$. Si pour toute paire \{x,y\} de sommets non adjacents, on a $d(x) + d(y) \geqslant n$, alors G est hamiltonien.L'assertion proposée est vraie ou fausse\\

Q. 88. Un graphe hamiltonien ne possède pas de sommets de degré 3.\\

Q. 89. Un graphe est dit simple, s’il ne contient pas de boucles et s’il n’y a pas plus d’une arête reliant deux mêmes sommets.\\

Q. 90. $K_2$ est hamiltonien.\\

Q. 91. Le graphe suivant est régulier.

\begin{center}
\includegraphics[scale=0.7]{figures/arbre1.eps}
\end{center}

Q. 92. Un graphe hamiltonien ne possède pas de sommets de degré 2.L'assertion proposée est vraie ou fausse\\

Q. 93.
\begin{center}
\includegraphics[scale=0.7]{figures/graphe8.eps}
\end{center}

est un graphe partiel de

\begin{center}
\includegraphics[scale=0.7]{figures/graphe7.eps}
\end{center}

Q. 94. Le corollaire de Dirac se déduit du théorème de Ore.\\

Q. 95. Un graphe simple a un nombre impair de sommets de degré pair.\\

Q. 96. Le nombre maximal d'arêtes dans un graphe non orienté d'ordre $n$ qui ne possède pas d'arêtes parallèles, est de $\dfrac{n(n+1)}{2}$.\\

Q. 97. $K_n$ possède $n$ sommets.\\

Q. 98. Le lemme des poignées de mains dit que la somme des degrés des sommets est égale à deux fois le nombre d'arêtes.\\

Q. 99. $K_4$ est hamiltonien.\\

Q. 100.
Le graphe $G$ suivant :
\begin{center}
\includegraphics[scale=0.7]{figures/graphe1b.eps}
\end{center}

\noindent Possède pour liste d'adjacence :

1 : 3, 4, 5

2 : 3

3 : 1, 2, 5

4 : 1, 3, 5

5 : 1, 3, 4\\

\end{document}
